<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      var advantageCount = function (nums1, nums2) {
        // 方法一：暴力法（时间超限）---时间：O（）（）---空间：O（）（）
        // const originNums2 = [...nums2];
        // const result = [];
        // let left1 = 0;
        // let right1 = nums1.length - 1;
        // let right2 = nums2.length - 1;
        // nums1.sort((a, b) => a - b);
        // nums2.sort((a, b) => a - b);
        // while (right2 >= 0) {
        //   if (nums1[right1] > nums2[right2]) {
        //     result[right2] = nums1[right1];
        //     right1--;
        //   } else {
        //     result[right2] = nums1[left1];
        //     left1++;
        //   }
        //   right2--;
        // }
        // // 把顺序调整到和originNums2一致
        // const res = [];
        // for (let i = 0; i < originNums2.length; i++) {
        //   const index = nums2.indexOf(originNums2[i])
        //   res[i] = result[index];
        //   nums2[index] = -1; // 标记已使用
        // }
        // return res;

        // 方法二：暴力法（空间换时间，时间超限，但是还是双重循环了，如果用对象的话，对象的key会覆盖而且不好重命名，还会改变顺序）---时间：O（）（）---空间：O（）（）
        // const originArr = [];
        // for (let i = 0; i < nums2.length; i++) {
        //   originArr.push([nums2[i],i]); // 记录nums2的顺序，方便后续还原顺序
        // }
        // const result = [];
        // let left1 = 0;
        // let right1 = nums1.length - 1;
        // let right2 = nums2.length - 1;
        // nums1.sort((a, b) => a - b);
        // nums2.sort((a, b) => a - b);
        // while (right2 >= 0) {
        //   if (nums1[right1] > nums2[right2]) {
        //     result[right2] = nums1[right1];
        //     right1--;
        //   } else {
        //     result[right2] = nums1[left1];
        //     left1++;
        //   }
        //   right2--;
        // }
        // // 把顺序调整到和原来一致
        // const res = [];
        // let count = -1
        // for (let i = 0; i < nums2.length; i++) {
        //   outer:for (let j = 0; j < originArr.length; j++) {
        //     if(originArr[j][0] === nums2[i]){
        //       res[originArr[j][1]] = result[i];
        //       originArr[j][0] = count--
        //       break outer
        //     }
        //   }
        // }
        // return res;

        // 方法三：暴力法（排序坐标）---时间：O（）（）---空间：O（）（）
        const n = nums1.length;
        const idx1 = Array(n).fill(0);
        const idx2 = Array(n).fill(0);
        const res = []
        for (let i = 0; i < n; ++i) {
          idx1[i] = i;
          idx2[i] = i;
        }
        // 既升序了，还没破坏原数组的顺序
        // 8 12 24 32
        // 2 0 1 3
        idx1.sort((a, b) => nums1[a] - nums1[b]);
        // 11 13 25 32
        // 3 0 1 2
        idx2.sort((a, b) => nums2[a] - nums2[b]);
        let left = 0
        let right = n - 1;
        for(let i = n-1; i>=0; i--){
          if(nums1[idx1[right]] > nums2[idx2[i]]){
            res[idx2[i]] =  nums1[idx1[right]];
            right--;
          }else{
            res[idx2[i]] = nums1[idx1[left]];
            left++;
          }
        }
        return res;
      };
      // 8 12 24 32
      // 11 13 25 32
      // 12 24 32 8
      // 不需要结果数组
      // 两个数组按照下标排序
      // 1 2 0 3
      // 1 2 3 0
      // console.log(advantageCount([2, 7, 11, 15], [1, 10, 4, 11]));
      console.log(advantageCount([12, 24, 8, 32], [13, 25, 32, 11]));
      // 0 1 2 2 4
      // 0 0 1 2 3
      // 1 2 2 0 4
      // console.log(advantageCount([2, 0, 4, 1, 2], [1, 3, 0, 0, 2]));
    </script>
  </body>
</html>
